﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace P2PFileScheduling
{
    public class Digraph
    {
        public int V { get { return this.sources.Count()+1; } }
        public int E { get { return edgeCount; } }
        public List<Vertex> sources = new List<Vertex>();
        public List<Vertex> sinks = new List<Vertex>();
        public List<List<DirectedEdge>> adj = new List<List<DirectedEdge>>();
        public List<List<Vertex>> fileOwners = new List<List<Vertex>>();
        public Vertex superSource;
        public Vertex superSink;
        public int NumFilePieces { get; set; }
        int edgeCount = 0;

        public Digraph(string input_path)
        {
            this.parse(input_path);

            foreach (Vertex v in sources)
                sinks.Add(v);

            bool[] source = new bool[this.fileOwners.Count()];

            for (int i = 0; i < this.fileOwners.Count(); i++)
                source[i] = true;

            superSource = new Vertex(0, "Source", -1, -1, source);
            superSink = new Vertex(this.V, "Sink", -1, -1, new bool[this.fileOwners.Count()]);

            this.sources.Insert(0, superSource);
            this.sinks.Insert(0, superSink);

            adj.Add(new List<DirectedEdge>());
            adj.Add(new List<DirectedEdge>());

            for (int i = 0; i < this.fileOwners.Count(); i++)
                fileOwners[i].Add(superSource);

            buildEdges();
        }

        /**
         * Add Vertex to graph
         */
        public void addVertex(int id, string name, int upload, int download, bool[] pieces)
        {
            Vertex v = new Vertex(id, name, upload, download, pieces);
            addVertex(v);
        }

        public void buildEdges()
        {
            foreach (Vertex s in sinks)
            {
                for (int i = 0; i < s.pieces.Count(); i++)
                {
                    if (s.pieces[i] == false)
                    {
                        List<Vertex> lv = fileOwners[i];
                     
                        foreach (Vertex v in lv)
                        {
                            if (v == superSource || s == superSink )
                                continue;

                            DirectedEdge edge = new DirectedEdge(this, v, s, 0, i);
                            addEdge(edge);
                        }
                    }
                }
            }

            //add edges from superSource to all other sources

            for (int i = 1; i < sources.Count; i++)
            {
                for (int j = 0; j < NumFilePieces; j++)
                {
                    DirectedEdge edge = new DirectedEdge(this, superSource, sources[i], 0, j);
                    addEdge(edge);
                }
            }

            //add edges from all other sources to superSink
            for (int i = 1; i < sinks.Count; i++)
            {
                for (int j = 0; j < NumFilePieces; j++)
                {
                    DirectedEdge edge = new DirectedEdge(this, sinks[i], superSink, 0, j);
                    addEdge(edge);
                }
            }

        }

        /**
          * Copy constructor.
          */
        public Digraph(Digraph G)
            : this(G.V)
        {
            for (int v = 0; v < G.V; v++)
            {
                // reverse so that adjacency list is in same order as original
                Stack<DirectedEdge> reverse = new Stack<DirectedEdge>();
                foreach (DirectedEdge e in G.adj[v])
                    reverse.Push(e);

                foreach (DirectedEdge e in reverse)
                    adj[v].Add(e);
            }
        }

        /**
         * Create an empty edge-weighted digraph with V vertices.
         */
        public Digraph(int V)
        {
            adj = new List<List<DirectedEdge>>();
            for (int v = 0; v < V; v++)
                adj[v] = new List<DirectedEdge>();
        }

        /**
         * Change edge weitgh
         */
        public void changeEdge(DirectedEdge e, int WeightChange, int type)
        {
            for (int i = 0; i < adj[e.from().number].Count; i++)
            {
                if (adj[e.from().number][i].to() == e.to() && e.type == type)
                    adj[e.from().number][i].flow += WeightChange;
            }
        }

        /**
         * Change edge weight
         */
        public void changeEdge(int from, int to, int WeightChange)
        {
            for (int i = 0; i < adj[from].Count; i++)
            {
                if (adj[from][i].to().number == to)
                {
                    adj[from][i].flow += WeightChange;
                    break;
                }
            }
        }

        /**
         * Change edge weight
         */
        public DirectedEdge getEdge(int from, int to)
        {
            for (int i = 0; i < adj[from].Count; i++)
            {
                if (adj[from][i].To.number == to)
                    return adj[from][i];
            }
            return null;
        }

        /**
          * Add the directed edge e to this digraph.
          */
        public void addEdge(DirectedEdge e)
        {
            int v = e.from().number;
            int w = e.to().number;
            adj[v].Add(e);
            ++edgeCount;
        }

        public void addVertex(Vertex v)
        {
            sources.Add(v);
            adj.Add(new List<DirectedEdge>());
        }

        public Vertex GetVertex(int i)
        {
            if (i == superSource.number)
                return superSource;

            if (i == superSink.number)
                return superSink;

            return sources[i];
        }

        /**
          * Return the edges incident from Vertex v as an Iterable.
          * To iterate over the edges incident from Vertex v in digraph G, use foreach notation:
          * <tt>for (DirectedEdge e : G.adj(v))</tt>.
          */
        public List<DirectedEdge> adjacent(int v)
        {
            return adj[v];
        }

        /// <summary>
        /// Returns all adjacent vertices for v for the given type.
        /// The depth argument ensures that only paths of length 3
        /// are returned
        /// </summary>
        /// <param name="v">The source vertex</param>
        /// <param name="type">The file type</param>
        /// <param name="depth">The depth of the BFS algorithm</param>
        /// <returns>All adjacent edges that conform to the specified criteria</returns>
        public List<DirectedEdge> adjacentTyped(int v, int type, int depth)
        {
            List<DirectedEdge> result = new List<DirectedEdge>();

            foreach (DirectedEdge e in adj[v])
            {
                if (depth == 0)
                    result.Add(e);
                else if (depth == 1 && e.To.number != superSink.number)
                    result.Add(e);
                else if (depth == 2 && e.To.number == superSink.number)
                    result.Add(e);
            }

            return result;
        }

        /**
          * Return all edges in this digraph as an Iterable.
          * To iterate over the edges in the digraph, use foreach notation:
          * <tt>for (DirectedEdge e : G.edges())</tt>.
          */
        public List<DirectedEdge> edges()
        {
            List<DirectedEdge> list = new List<DirectedEdge>();

            for (int v = 0; v < V; v++)
            {
                foreach (DirectedEdge e in adj[v])
                {
                    list.Add(e);
                }
            }
            return list;
        }

        /**
          * Return number of edges incident from v.
          */
        public int outdegree(int v)
        {
            return adj[v].Count;
        }

        /**
          * Return a string representation of this graph.
          */
        public String toString()
        {
            String NEWLINE = "\r\n";
            StringBuilder s = new StringBuilder();
            s.Append(V + " " + E + NEWLINE);

            for (int v = 0; v < V; v++)
            {
                s.Append(v + ": ");
                
                foreach (DirectedEdge e in adj[v])
                    s.Append(e.To.number + "(type: " + e.type + ", flow: " + e.flow + ", cap: " + e.capacity + ")" + "  ");

                s.Append(NEWLINE);
            }
            return s.ToString();
        }

        public List<DirectedEdge> getEdges(int type, Vertex v)
        {
            List<DirectedEdge> adjacentEdges = adjacent(v.number);
            List<DirectedEdge> temp = new List<DirectedEdge>();

            foreach(DirectedEdge e in adjacentEdges) 
            {
                if(e.type == type) 
                    temp.Add(e);
            }

            return temp;
        }

        public bool IsDone()
        {
            for (int i = 0; i < sinks.Count; ++i)
            {
                if (!sinks[i].pieces.All(x => x == true))
                    return false;
            }

            return true;
        }

        public void parse(string input_path)
        {
            string[] lines = File.ReadAllLines(input_path);
            string[] splitted = lines[0].Split(' ');
            int n = Int32.Parse(splitted[0]);
            int f = Int32.Parse(splitted[1]);
            NumFilePieces = f;
            
            for (int i = 0; i < n; i++)
            {
                splitted = lines[i + 1].Split(' ');
                string[] filepieces = lines[i + n + 1].Split(' ');
                bool[] pieces = new bool[f];

                for (int j = 1; j < filepieces.Length; j++)
                    pieces[Int32.Parse(filepieces[j])] = true;

                this.addVertex(this.V, splitted[0], Int32.Parse(splitted[1]), Int32.Parse(splitted[2]), pieces);
            }

            for (int i = 0; i < f; i++)
            {
                fileOwners.Add(new List<Vertex>());

                foreach (Vertex v in sources)
                {
                    for (int j = 0; j < v.pieces.Length; j++)
                    {
                        if (j == i && v.pieces[j] == true)
                            fileOwners[i].Add(v);
                    }
                }
            }
        }
    }
}